package com.wujian.love.study.sufa;

import java.util.Arrays;

/**
 * @ClassName: Solution
 * @Description: 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
 * 输入: 5
 * 输出: [0,1,1,2,1,2]
 * @Author: wuj
 * @Date: 2021-03-03 15:14
 * <p>
 * 解题思路
 * 对于所有的数字，只有两类：
 * <p>
 * 奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。
 * <p>
 * 举例：
 * 0 = 0       1 = 1
 * 2 = 10      3 = 11
 * <p>
 * 偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。
 * 因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。
 * <p>
 * 举例：
 * 2 = 10       4 = 100       8 = 1000
 * 3 = 11       6 = 110       12 = 1100
 * <p>
 * 1: 0001     3:  0011      0: 0000
 * 2: 0010     6:  0110      1: 0001
 * 4: 0100     12: 1100      2: 0010
 * 8: 1000     24: 11000     3: 0011
 * 16:10000    48: 110000    4: 0100
 * 32:100000   96: 1100000   5: 0101
 * <p>
 * 由上可见：
 * 1、如果 i 为偶数，那么f(i) = f(i/2) ,因为 i/2 本质上是i的二进制左移一位，低位补零，所以1的数量不变。
 * 2、如果 i 为奇数，那么f(i) = f(i - 1) + 1， 因为如果i为奇数，那么 i - 1必定为偶数，而偶数的二进制最低位一定是0，
 * 那么该偶数 +1 后最低位变为1且不会进位，所以奇数比它上一个偶数bit上多一个1，即 f(i) = f(i - 1) + 1。
 **/
public class Solution {

    public static void main(String[] args) {
        int[] ints = countBits(20);
        System.out.println(Arrays.toString(ints));
    }

    private static int[] countBits(int num) {
        int[] arr = new int[num + 1];
        arr[0] = 0;
        for (int i = 1; i <= num; i++) {
            if (i % 2 == 1) {
                arr[i] = arr[i - 1] + 1;
            } else {
                arr[i] = arr[i / 2];
            }

        }
        return arr;
    }
}
